package com.cqs.leetcode.tree;

import com.cqs.leetcode.TreeNode;

/**
 * lixw
 * 2021/11/4
 **/
public class DiameterBinaryTree543 {


    private int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        high(root);
        //边的数量 比结点的数量少1
        return max - 1;
    }


    private int high(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = high(node.left);
        int r = high(node.right);
        max = Math.max(l + r + 1, max);
        return 1 + Math.max(l, r);
    }
}
